#!/usr/env/bin python
# -*- coding: utf-8 -*-
# filename: treap.py
# creator: yangdy
# create date: 2018/3/30
"""  
treap
TODO模块说明
Public Class:
-	TODO类名: TODO类说明 
Public Methods: 
-	TODO方法名: TODO方法说明
"""
from random import randint
MAX_H = 10000


class Tree:
    class TreeNode:
        def __init__(self, val):
            self.val = val
            self.right = None
            self.left = None
            self.n = 1
            self.h = randint(0, MAX_H)

    def __init__(self):
        self.root = None

    def left_rotate(self, p=None):
        if not p or not p.left:
            return
        l = p.left
        p.val, l.val = l.val, p.val
        p.n, l.n = l.n, p.n
        p.h, l.h = l.h, p.h
        p.left = l.left
        l.left = l.right
        l.right = p.right
        p.right = l

    def right_rotate(self, p=None):
        if not p or not p.right:
            return
        r = p.right
        p.val, r.val = r.val, p.val
        p.n, r.n = r.n, p.n
        p.h, r.h = r.h, p.h
        p.right = r.right
        r.right = r.left
        r.left = p.left
        p.left = r

    def add(self, val):
        if not self.root:
            self.root = self.TreeNode(val)
            return

        def _add_work(val, p=self.root):
            if val > p.val:
                if not p.right:
                    p.right = self.TreeNode(val)
                else:
                    _add_work(val, p.right)
                if p.h < p.right.h:
                    self.right_rotate(p)
            elif val < p.val:
                if not p.left:
                    p.left = self.TreeNode(val)
                else:
                    _add_work(val, p.left)
                if p.h < p.left.h:
                    self.left_rotate(p)
            else:
                p.n += 1
        _add_work(val)

    def remove(self, val):
        if not self.root:
            return

        def _remove_work(val, p=self.root, q=None):
            if val > p.val:
                if p.right:
                    _remove_work(val, p.right, p)
            elif val < p.val:
                if p.left:
                    _remove_work(val, p.left, p)
            else:
                if p.n > 1:
                    p.n -= 1
                elif p.left and p.right:
                    x, y, p.val = p.right, None, p.right.val
                    while x.left:
                        x, y = x.left, x
                    if y:
                        y.left = x.right
                    else:
                        p.right = x.right
                elif p.left or p.right:
                    e = p.left if p.left else p.right
                    p.val, p.left, p.right = e.val, e.left, e.right
                else:
                    if q and q.left==p:
                        q.left = None
                    elif q:
                        q.right = None
                    else:
                        self.root = None
        _remove_work(val)

    def find(self, val):
        def _find_work(val, p=self.root):
            if not p:
                return False
            if val < p.val:
                return _find_work(val, p.left)
            elif val > p.val:
                return _find_work(val, p.right)
            else:
                return True
        return _find_work(val)

    def display(self):
        def _display_work(p=self.root, dep=0):
            if not p:
                return
            _display_work(p.right, dep+1)
            print(' '*dep+'%d:%d(%d)' % (p.val, p.n, p.h))
            _display_work(p.left, dep+1)
        work = _display_work()


def main():
    print('main start...')
    tree = Tree()
    # tree.add(1)
    # tree.display()
    # for i in range(10):
    #     x = randint(0, 1000)
    #     print('x='+str(x))
    #     tree.add(x)
    #     print('-----')
    #     tree.display()
    #     print('-----')
    for i in range(10):
        tree.add(i)
        print('add i=%d' % i)
        tree.display()
        print('-----')
    for i in range(9, -1, -1):
        tree.remove(i)
        print('remove i=%d' % i)
        tree.display()
        print('-----')


if __name__ == '__main__':
    main()
